/**
 * Compute the prime factorization of a given number
 * 
 * @author Jon Ludwig
 *
 */

import java.math.*;
import java.util.*;

public class Factor {

	/**
	 * Computer the prime factorization of a number
	 * 
	 * @param a
	 * @return
	 */
	public static ArrayList<ExpNumber> factor(BigInteger a)
	{
		ArrayList<ExpNumber> factors = new ArrayList<ExpNumber>();
		
		ExpNumber current;
		BigInteger two = BigInteger.valueOf(2L);
		
		
		// skip even numbers
		
		for (BigInteger i = two; i.compareTo(a) <= 0; i = i.add(two))
		{
			current = new ExpNumber();
			current.base = i;
			current.exponent = BigInteger.ZERO;
			
			while (a.mod(i).compareTo(BigInteger.ZERO) == 0)
			{
				a = a.divide(i);
				current.exponent = current.exponent.add(BigInteger.ONE);
				
				//System.out.println(i);
			}
			
			if (current.exponent.compareTo(BigInteger.ZERO) > 0)
				factors.add(current);
			
			// two is the only even number to test
			if (i.compareTo(two) == 0)
				i = i.subtract(BigInteger.ONE);
		}
		
		return factors;
	}
	
	/**
	 * Main entry point
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		if (args.length < 1) {
			System.out.println("usage: java Factor a");
		}
		
		BigInteger a = new BigInteger(args[0]);
		
		ArrayList<ExpNumber> factors = factor(a);
		if (factors.isEmpty() == false)
		{
			ExpNumber n = factors.get(0);
			System.out.print(n.base + "^" + n.exponent);
			for (int i = 1; i < factors.size(); i++)
			{
				n = factors.get(i);
				//System.out.print(" * " + n.base + "^" + n.exponent);
			}
			
			//System.out.println();
		}
	}
	
	/**
	 * Base and exponent
	 *
	 */
	public static class ExpNumber
	{
		public BigInteger exponent;
		public BigInteger base;
	}

}
